#include <stdio.h>
/*
希尔排序的基本思想是先取一个小于n的整数d1作为第一个增量，
把全部元素分组。所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；然后，取第二个增量d2 < d1重复上述的分组和排序，
直至所取的增量 =1( < …< d2 < d1)，即所有记录放在同一组中进行直接插入排序为止，
希尔排序主要是根据插入排序的一下两种性质对插入排序进行改进：
1)插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2)但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
*/
void shellSort(int arr[], int n)
{
    int num = 0;

    int i, j, elem;
    int k = n / 2;
    //基于一种简单的增量分组方式｛n/2,n/4,n/8……,1｝
    while (k >= 1)
    {
        /*
        初始值5和0替换
        然后6和1替换
        7和2
        8和3
        9和4
        */
        for (i = k; i < n; i++)
        {
            elem = arr[i];

            for (j = i; j >= k; j -= k)
            {
                num++;
                printf("执行次数%d", num);
                if (elem < arr[j - k])
                {
                    arr[j] = arr[j - k];
                }
                else
                {
                    break;
                }
            }
            arr[j] = elem;
        }
        k = k / 2;
    }
}

void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return;
}

void main()
{
    int arr[10] = {2, 5, 6, 4, 3, 7, 9, 8, 1, 0};
    printArray(arr, 10);
    shellSort(arr, 10);
    printArray(arr, 10);
    return;
}